package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/19 15:46
 * @description :6道
 * 状态低迷的一天。
 * persevere to last
 * 2021.11.19
 * 李红磊
 * 2021年11月19日21:13:25
 */
public class t20211119 {

    //397.整数替换
    public int integerReplacement(int n) {
        long num = n;
        int res = 0;
        while (num != 1) {
            if ((num & 1) == 0) num >>= 1;
            else {
                if (num != 3 && ((num >> 1) & 1) == 1) num++;
                else num--;
            }
        }
        return res;
    }

    //剑指57.和为s的两个数字
    public int[] twoSum(int[] nums, int target) {
        if (nums == null) return new int[0];
        HashSet<Integer> hashSet = new HashSet() {{
            add(nums[0]);
        }};

        for (int i = 1; i < nums.length; i++) {
            int tem = target - nums[i];
            if (hashSet.contains(tem)) return new int[]{tem, nums[i]};
            else hashSet.add(nums[i]);
        }
        return new int[0];
    }

    public int[] twoSum2(int[] nums, int target) {
        if (nums == null) return new int[0];

        int len = nums.length, left = 0, right = len - 1;
        int mid = left + right >>> 1;
        while (mid < len - 1 && left < right) {

            if (nums[mid] >= target) break;
            else mid++;
        }

        right = mid;

        while (left <= right) {
            if (nums[left] + nums[right] == target) return new int[]{nums[left], nums[right]};
            right--;
        }
        return new int[0];
    }

    //剑指58。翻转单词顺序
    public String reverseWords(String s) {
        if (s == null) {
            return null;
        }
        String[] split = s.split(" ");
        StringBuffer buffer = new StringBuffer();
        int len = split.length;
        for (int i = len - 1; i >= 0; i--) {
            String temp = split[i];
            if (!temp.equals("")) {
                int count = i;
                while (count >= 1) {
                    if (!split[count - 1].equals("")) {
                        buffer.append(temp).append(" ");
                        break;
                    }
                    count--;
                }
                buffer.append(temp);
            } else {
                if (i == len - 1 || i == 0) continue;
                if (i - 1 >= 0 && split[i - 1].equals("")) continue;
                buffer.append(temp);
            }
        }

        return buffer.toString();
    }

    //剑指12.矩阵中的路径
    public boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int rows = board.length, columns = board[0].length;
        boolean[][] visit = new boolean[rows][columns];
        char firstLetter = word.charAt(0);

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == firstLetter) {
                    if (dfs(i, j, 0, visit, word, board)) return true;
                }
            }
        }
        return false;
    }
    /**
     * @Author 李红磊
     * @Date 2021/11/19 17:46
     * @param: x
     * @param: y
     * @param: cur 当前检索到的字母下标
     * @param: visit
     * @param: word
     * @param: board
     **/
    private boolean dfs(int x, int y, int cur, boolean[][] visit, String word, char[][] board) {
        if (cur == word.length() - 1) {
            return board[x][y] == word.charAt(word.length() - 1);
        }
        if (board[x][y] != word.charAt(cur)) return false;

        visit[x][y] = true;

        int[] dir = {-1, 0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i];
            int newY = y + dir[i + 1];
            if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length && !visit[newX][newY]) {
                if (dfs(newX, newY, cur + 1, visit, word, board)) return true;
            }

        }
        visit[x][y] = false;
        return false;
    }

    //剑指13.机器人的运动范围
    int m, n;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        boolean[][] visit = new boolean[m][n];

        int res = sport(0, 0, k, visit);

        return res;
    }
    private int sport(int x, int y, int k, boolean[][] visit) {
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || visit[x][y]) return 0;
        //判断数位之和
        //拿个位
        int x_ge = x / 1 % 10;
        int y_ge = y / 1 % 10;
        //拿十位
        int x_shi = x / 10 % 10;
        int y_shi = y / 10 % 10;
        if (x_ge + x_shi + y_ge + y_shi > k) return 0;
        visit[x][y] = true;


        return 1 + sport(x - 1, y, k, visit) +
                sport(x + 1, y, k, visit) +
                sport(x, y - 1, k, visit) +
                sport(x, y + 1, k, visit);
    }

    //剑指34.二叉树中和为某一值的路径
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        if (root.right == null && root.left == null) {
            if (root.val == target) {
                ArrayList<Integer> temp = new ArrayList() {{
                    add(root.val);
                }};
                res.add(temp);
                return res;
            }
            return res;
        }

        test(root.left, res, new ArrayList() {{
            add(root.val);
        }}, target);
        test(root.right, res, new ArrayList() {{
            add(root.val);
        }}, target);
        return res;
    }
    private void test(TreeNode root, List<List<Integer>> res, List<Integer> cur, int target) {
        if (root == null) return;

        cur.add(root.val);
        int tem = 0;
        for (Integer o : cur) {
            tem += o;
        }
        if (tem == target && root.left == null && root.right == null) res.add(new ArrayList<>(cur));

        test(root.left, res, cur, target);
        test(root.right, res, cur, target);
        cur.remove(cur.size() - 1);

    }

    LinkedList<List<Integer>> res;
    public List<List<Integer>> pathSum2(TreeNode root, int target) {
        res = new LinkedList<>();
        if (root == null) return res;
        if (root.left == null && root.right == null) {
            if (root.val == target) {
                LinkedList tem = new LinkedList() {{
                    add(root.val);
                }};
                res.addLast(tem);
                return res;
            }
            return res;
        }
        test2(root, target, new LinkedList<Integer>());
        return res;
    }
    private void test2(TreeNode root, int target, LinkedList<Integer> path) {
        if (root == null) return;
        path.addLast(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.addLast(new LinkedList<>(path));
        }
        test2(root.left, target, path);
        test2(root.right, target, path);
        path.removeLast();
    }


    public static void main(String[] args) {
        t20211119 t20211119 = new t20211119();
        TreeNode root = new TreeNode(5);

        //left
        TreeNode node1 = new TreeNode(4);
        TreeNode node3 = new TreeNode(11);
        node1.left = node3;
        TreeNode node4 = new TreeNode(7);
        node3.left = node4;
        TreeNode node5 = new TreeNode(2);
        node3.right = node5;

        root.left = node1;

        t20211119.pathSum(root, 22).stream().forEach(s -> System.out.println(s));

        LinkedList<Object> list = new LinkedList<>();

    }
}
